<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>SCC</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">强连通分量</h1>
<h5 id="toc-1">如果图中两个结点可以相互通达，则称两个结点强连通。</h5>
<h5 id="toc-2">如果有向图G的每两个结点都强连通，称G是一个强连通图。</h5>
<h5 id="toc-3">有向图的极大强连通子图（没有被其他强连通子图包含），称为强连通分量。</h5>
<hr>
<p>强连通分量？</p>
<p>不存在的。</p>
<hr>
<h3 id="toc-4">一、Kosaraju</h3>
<p>因为是有向图，所以我们可以选择一种绝世的苟法，对于所有的边去建一个反边，与当前方向相反的边，然后dfs就好了</p>
<p>思路是这个思路，但是具体对于题是什么样的？</p>
<p><img src="http://ww4.sinaimg.cn/large/0060lm7Tly1fjsbxyla05j30hs078q4o.jpg" alt="image"></p>
<p>对于这两个强连通分量而言，我们对其建立反向边，如图：</p>
<p><img src="http://ww4.sinaimg.cn/large/0060lm7Tly1fjsbyxrog3j30hs072q3i.jpg" alt="image"></p>
<p>该怎么样愉快地cao这个强连通分量呢，就是先把他dfs一遍，求一下dfn序，也就是加个时间戳，也就是走到这个点的先后顺序，因为对于强连通分量而言，从任意一个点进入，可以到达这个强连通分量的所有包含的点，所以我们先建立一个反向边。然后按照这个DFN序的大小开始跑反图，从dfn序大的往dfn序小的地方跑，然后简单的统计个数就好了</p>
<h3 id="toc-5">二、Tarjan</h3>
<p>万能的Tarjan又来啦，对于求强连通分量，Tarjan无疑是选择人数最多的做法，10个AC,8个Tarjan，1个Kosaraju，还有一个大暴力</p>
<p>所以暴力是有希望的啊</p>
<p>所以Tarjan是什么？</p>
<h4 id="toc-6">Tarjan思路：</h4>
<p>定义dfn存放时间戳，low存放节点和搜索树中下方子树根节点，找到未被访问的点时就进栈，找到一个强连通分量的根节点的时候，就把目前点到栈顶的所有点全都弹出来。</p>
<p>啊思路好难讲啊，看看代码吧</p>
<pre><code>#include&lt;iostream&gt;
#include&lt;cstdio&gt;
#include&lt;algorithm&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
using namespace std;
template&lt;class T&gt;void read(T &amp;x){
    x=0;int f=0;char ch=getchar();
    while(ch&lt;'0'||ch&gt;'9'){f|=(ch=='-');ch=getchar();}
    while(ch&lt;='9'&amp;&amp;ch&gt;='0'){x=(x&lt;&lt;1)+(x&lt;&lt;3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}

#define maxn 10010
#define maxm 50010
int dfn[maxn],low[maxn],vis[maxn],belong[maxn],out[maxn];
int size[maxn],head[maxn],instack[maxn],stack[maxn];
int ecnt,tot,pos,orz,cnt,top;

struct edge{
    int u,v,next;
}E[maxm];

void addedge(int u,int v){
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].next=head[u];
    head[u]=ecnt;
}

void Tarjan(int x)
{
    dfn[x]=low[x]=++orz;//加时间戳
    stack[++top]=x;//压进栈
    instack[x]=1;
    for(int i=head[x];i;i=E[i].next){//遍历整个表
        int v=E[i].v;
        if(!dfn[v]) Tarjan(v);//向下遍历
        if(instack[v]) low[x]=min(low[v],low[x]);//在栈里的每一个元素都要更新一下low值，保证统一
    }
    if(dfn[x]==low[x]){//所有点跑完之后回溯到原来的点，就是开始Tarjan的那个点，目前栈里所有low的出发点
        ++tot;int v;//统计强连通分量的个数
        do{
            v=stack[top--];//弹出栈
            instack[v]=0;
            belong[v]=tot;//这个点属于哪一个强连通分量
            size[tot]++;//这个强连通分量的大小（题中说的有多少牛被所有牛喜欢）
        }while(v!=x);//所有的弹出
    }
}
void dfs(int x){
    vis[x]=1;//打标记
    for(int i=head[x];i;i=E[i].next){
        int v=E[i].v;//遍历表
        if(belong[v]!=belong[x]) out[belong[x]]++;//两个点不在一个强连通分量中，那么第一个的出度++
        if(!vis[v]) dfs(v);//继续往下
    }
}
void work(){
    for(int i=1;i&lt;=n;i++)
        if(!dfn[i]) Tarjan(i);//去给每一个点建立dfn
    for(int i=1;i&lt;=n;i++)
        if(!vis[i]) dfs(i);//跑DAG图
    for(int i=1;i&lt;=tot;i++)//遍历每一个强连通分量
        if(!out[i]) cnt++,pos=i;//找到一个出度为0的，统计一下
}
int main()
{
    int n,m;
    read(n),read(m);
    for(int i=1;i&lt;=m;i++){
        int u,v;
        read(u),read(v);
        addedge(u,v);//单向边
    }
    work();
    if(cnt==1) printf("%d\n",size[pos]);//刚好所有的都喜欢他，那就输出这个牛群
    else puts("0");//有一堆那就是0
    return 0 ;
}</code></pre>
<p>那就完喽？</p>
<h2 id="toc-7">by:Wahacer</h2>
<h2 id="toc-8">特别鸣谢：xqmmcqs、Haild、uncle-lu</h2>
<h2 id="toc-9">尤其鸣谢：五十岚芒果干（jiang</h2>
<p>2017年9月22号</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>